Halftoning is a technique used in printing images. Currently, there are various methods to halftone an image. In general terms, halftoning converts a continuous tone image to a multilevel image. The simplest halftoning method merely rounds each pixel to either black or white, corresponding to ink dot on and ink dot off respectively. For example, a one-dimensional two-level quantizer, Q(x) is the rounding function, where x is a number between 0 and 1. When x is less than 0.5, Q(x) is set to 1. Otherwise, Q(x), is set to 0. Suppose f[i,j] is the original continuous tone image brightness at position [i,j] in an image. The simplest halftoning method rounds off the brightness value, which can be expressed as Halftone[i,j]=Q(f[i,j]). However, this simple halftoning method does not preserve sufficient image characteristics. For example, suppose black corresponds to 1 and white corresponds to 0. If the original image is a block of gray with a value of 0.3, then the above halftoning method would simply round off the value of 0.3 to 0, which corresponds to white, and thus, resulting in a completely white halftoned image.
To preserve more image characteristics, more complex halftoning methods were developed by adding noise, n[i,j], to the input signal at position [i,j] before quantizing. Two halftoning methods that add noise to the input signal are dithering and error diffusion. Dithering adds noise to an input signal according to a dither matrix. The dither matrix is a grid with a number of slots. Each slot has a numeric entry. The dither matrix is tessellated over the input image. The noise added to an input signal at position [i,j] is determined by an entry in the dither matrix, where the entry is within a slot covering the position [i,j] of the image. Using entries in the dither matrix speeds up halftoning because the input data can be processed in parallel. However, using entries in the dither matrix is also a drawback of dithering because the entries do not take into account of the results of the halftoning of neighboring pixels within the image, leading to a halftoned image of lower quality.
Error diffusion adds noise to an input signal differently than dithering. Instead of using a matrix to determine the amount of noise to add to input signals of an image, error diffusion iterates in raster order through all the pixels of the image. The noise added to each pixel is filtered feedback from the quantization errors that occurred in the neighboring pixels that were already quantized. The image quality of error diffusion overall is better than dithering because error diffusion takes into account of feedback from neighboring pixels. In particular, edges of error-diffused images are sharper and contours appear more natural.
Although error diffusion produces better overall image quality, there are a number of disadvantages in error diffusion. First, error-diffused images tend to appear grainy in low-density ink areas. Error diffusion can also cause worm-like artifacts. Moreover, error diffusion involves more calculations that are performed serially, and therefore, error diffusion is more time-consuming than dithering, which is performed in parallel. Furthermore, another problem with error diffusion is the large number of isolated dots that are produced. Isolated dots are dots without a neighboring dot of the same color. Isolated dots are difficult to print with laser printing technology at high resolution. Error diffusion creates isolated dots within a large proportion of an image, and therefore, many current printers usually have difficulties printing error-diffused images.
A combination of error diffusion and dither may lead to more efficient printing of high quality images.
U.S. Pat. No. 5,930,010 issued Jul. 27, 1999 sets forth a technique in which error diffusion is performed on the C, M, and K color planes, while dither is performed on the Y color plane.
U.S. Pat. No. 6,363,172, entitled “Combined Color Halftoning”, discloses combining the C and M planes for dither. First, the patent discloses dithering the C+M signal, which determines where C or M dots should be printed. Then the C signal is dithered with the same mask; since C<C+M, this determines which of the previously chosen dots should be C. The remaining dots are printed magenta. Only one dither mark needs to be used to dither both the C and M planes, with a dot-off-dot result. This patent also discloses an error diffusion variation, in which C+M undergoes error diffusion then if a dot should be printed, they ask ‘Is Ccurrent+Cerror>Mcurrent+Merror?’ That determines whether a C or M is printed there. The error passing must still occur for both the C and M planes, so this method is more computationally complex than standard error diffusion. The resulting halftone should exhibit more dot-off-dot printing. The patent also describes dither or error diffuse C+M, and then randomly deciding whether to print C or M at each chosen printing location.
U.S. Pat. No. 5,394,252 discloses using a periodic halftoning for some color planes and a non-periodic halftoning for other color planes with the intention for the halftoning to occur on the input color separations, which are the same as the output inks.